// https://www.lintcode.com/problem/bold-words-in-string/

public class Solution {
    /**
     * @param words: the words
     * @param S: the string
     * @return: the string with least number of tags
     */
    public String boldWords(String[] words, String S) {
        // Write your code here
        StringBuilder sb = new StringBuilder();
        boolean[] bold_marks = new boolean[S.length()];
        for (int i = 0; i < S.length(); ++i) {
            for (String word : words) {
                int wlen = word.length();
                if ((i + wlen) <= S.length()) {
                    if (S.substring(i, i + wlen).equals(word)) {
                        for (int j = i; j < (i + wlen); ++j) {
                            bold_marks[j] = true;
                        }
                    }
                }
            }
        }
        boolean is_bold = false;
        for (int i = 0; i < S.length(); ++i) {
            if ((bold_marks[i]) && (!is_bold)) {
                sb.append("<b>");
                is_bold = true;
            } else if ((!bold_marks[i]) && is_bold) {
                sb.append("</b>");
                is_bold = false;
            }
            sb.append(S.charAt(i));
        }
        if (is_bold) {
            sb.append("</b>");
        }
        return sb.toString();
    }
}